package main

/*
二叉树的最近公共祖先（二叉树）
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
*/

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归
func lowestCommonAncestor1(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == p.Val || root.Val == q.Val {
		return root
	}
	//递归找到 p q
	left := lowestCommonAncestor1(root.Left, p, q)
	right := lowestCommonAncestor1(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left == nil {
		return right
	}
	return left
}

//非递归
/*
迭代
利用类似哈希表求交集的思路解决。
我们可以用哈希表存储所有节点的父节点.然后对于p节点我们就可以利用节点的父节点信息向上遍历它的祖先节点(从父亲节点到爷爷节点一直到根节点),
并用集合visited记录已经访问过的节点.然后再从q节点也利用其父节点的信息向上跳,如果集合visited中碰到已经访问过的节点,那么该节点就是我们要
找的最近公共祖先。
*/
func lowestCommonAncestor2(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	parentDict := make(map[*TreeNode]*TreeNode)
	visited := make(map[int]bool)
	var dfs func(node *TreeNode)
	// dfs函数记录二叉树除根节点外所有节点的父亲节点
	dfs = func(node *TreeNode) {
		if node.Left != nil {
			parentDict[node.Left] = node
			dfs(node.Left)
		}
		if node.Right != nil {
			parentDict[node.Right] = node
			dfs(node.Right)
		}
	}
	dfs(root)
	for p != nil {
		visited[p.Val] = true
		p = parentDict[p]
	}
	for q != nil {
		if visited[q.Val] {
			return q
		}
		q = parentDict[q]
	}
	return nil
}

func main() {
	A := &TreeNode{Val: 3}
	A.Left = &TreeNode{Val: 5}
	A.Right = &TreeNode{Val: 1}
	A.Left.Left = &TreeNode{Val: 6}
	A.Left.Right = &TreeNode{Val: 2}
	A.Right.Left = &TreeNode{Val: 0}
	A.Right.Right = &TreeNode{Val: 8}
	A.Left.Right.Left = &TreeNode{Val: 7}
	A.Left.Right.Left = &TreeNode{Val: 4}
	fmt.Println(lowestCommonAncestor1(A, A.Left.Left, A.Left.Right.Left))
}
